import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class CatDogAsylum { // 猫狗收容问题

    public ArrayList<Integer> asylum(int[][] ope) {
        Queue<Integer> Dog = new LinkedList<>();//狗(所有正数)     +
        Queue<Integer> Cat = new LinkedList<>();//猫（所有负数）     -
        Queue<Integer> All = new LinkedList<>();//所有
        Queue<Integer> ToAll = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();//收养序列
        for (int i = 0; i < ope.length; i++) {
            if (ope[i][0] == 1) {
                All.offer(ope[i][0]);
                if (ope[i][1] > 0) {
                    Dog.offer(ope[i][1]);
                } else if (ope[i][1] < 0) {
                    Cat.offer(ope[i][1]);
                }

            } else if (ope[i][0] == 2) {
                if (ope[i][1] == 0) {   //出最早入栈的元素
                    if (!All.isEmpty()) {
                        int tmp = All.poll();
                        list.add(tmp);
                        if (tmp == Dog.peek()) {
                            Dog.poll();
                        } else if (tmp == Cat.peek()) {
                            Cat.poll();
                        }
                    }
                    return list;
                } else if (ope[i][1] == 1) { //出最先入栈的正数
                    if (!Dog.isEmpty()) {
                        int tmp = Dog.poll();
                        list.add(tmp);
                        for (int j = 0; j < All.size(); j++) {
                            if (All.peek() == tmp) {
                                All.poll();
                                break;
                            } else {
                                ToAll.offer(All.poll());
                            }
                        }
                        for (int k = ToAll.size(); k > 0; k--) {
                            All.offer(ToAll.poll());
                        }
                        for (int j = 0; j < All.size(); j++) {
                            All.offer(All.poll());
                        }
                    }
                } else if (ope[i][1] == -1) {
                    if (!Cat.isEmpty()) {
                        int tmp = Cat.poll();
                        list.add(tmp);
                        for (int j = 0; j < All.size(); j++) {
                            if (All.peek() == tmp) {
                                All.poll();
                                break;
                            } else {
                                ToAll.offer(All.poll());
                            }
                        }
                        for (int k = ToAll.size(); k > 0; k--) {
                            All.offer(ToAll.poll());
                        }
                        for (int j = 0; j < All.size(); j++) {
                            All.offer(All.poll());
                        }
                    }
                }
            }
        }
        return list;
    }

}
